package cc.wsyw126.java.lintCode.convert_binary_search_tree_to_doubly_linked_list;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * Created by junpeng.yang on 17/3/9.
 */
public class Solution {
    /**
     * @param root: The root of tree
     * @return: the head of doubly list node
     */
    public DoublyListNode bstToDoublyList(TreeNode root) {
        // Write your code here
        Stack<TreeNode> stack = new Stack<>();
        Queue<DoublyListNode> queue = new LinkedList<>();
        midSort(stack, root, queue);
        DoublyListNode begin = new DoublyListNode(0);
        begin.next = null;
        DoublyListNode temp = begin;

        DoublyListNode poll = queue.poll();
        while (poll != null) {
            temp.next = poll;
            poll.prev = temp;
            temp = poll;
            poll = queue.poll();
        }
        return begin.next;
    }

    public void midSort(Stack<TreeNode> stack, TreeNode node, Queue<DoublyListNode> queue) {
        if (node != null) {
            stack.push(node);
        } else return;
        midSort(stack, node.left, queue);
        TreeNode pop = stack.pop();
        DoublyListNode doublyListNode = new DoublyListNode(pop.val);
        queue.add(doublyListNode);
        midSort(stack, node.right, queue);
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(4);
        TreeNode treeNode1 = new TreeNode(2);
        TreeNode treeNode2 = new TreeNode(5);
        treeNode.left = treeNode1;
        treeNode.right = treeNode2;
        TreeNode treeNode3 = new TreeNode(1);
        TreeNode treeNode4 = new TreeNode(3);
        treeNode1.left = treeNode3;
        treeNode1.right = treeNode4;

        treeNode2.right = treeNode2.left = null;
        treeNode3.right = treeNode3.left = null;
        treeNode4.right = treeNode4.left = null;

        Solution solution = new Solution();
        DoublyListNode doublyListNode = solution.bstToDoublyList(treeNode);
        DoublyListNode temp = doublyListNode;
        while (temp != null) {
            System.out.println("temp.val = " + temp.val);
            temp = temp.next;
        }

    }
}
